package com.sam.lintcode;

/**
 * 给定一些 points 和一个 origin，从 points 中找到 k 个离 origin 最近的点。按照距离由小到大返回。如果两个点有相同距离，则按照x值来排序；若x值也相同，就再按照y值排序。
 */
//https://www.lintcode.com/problem/k-closest-points/description?_from=ladder&&fromId=47
public class KClose {

    static class Point {
        int x;
        int y;

        Point() {
            x = 0;
            y = 0;
        }

        Point(int a, int b) {
            x = a;
            y = b;
        }

        @Override
        public String toString() {
            return String.format("[%d,%d]", x, y);
        }
    }

    public static void main(String[] args) {
        KClose kClose = new KClose();
        System.out.println(
                kClose.kClosest(new Point[]{new Point(4, 4), new Point(2, 5), new Point(1, 1)}, new Point(), 3).toString()
        );

    }

    /**
     * @param points: a list of points
     * @param origin: a point
     * @param k:      An integer
     * @return: the k closest points
     */
    public Point[] kClosest(Point[] points, Point origin, int k) {
        // write your code here
        //output x = index y = d
        Point[] result = new Point[k];
        Point tmp;
        Point currentPoint;
        for (int i = 0; i < points.length; i++) {
            int d = (points[i].x - origin.x) * (points[i].x - origin.x) + (points[i].y - origin.y) * (points[i].y - origin.y);
            tmp = new Point(i, d);
            for (int j = 0; j < k; j++) {
                if (result[j] == null) {
                    result[j] = tmp;
                    break;
                } else {
                    currentPoint = result[j];
                    if (tmp.y < currentPoint.y
                            || (tmp.y == currentPoint.y && (points[tmp.x].x < points[currentPoint.x].x
                            || (points[tmp.x].x == points[currentPoint.x].x && points[tmp.x].y < points[currentPoint.x].y)))) {
                        result[j] = tmp;
                        tmp = currentPoint;
                    }
                }

            }
        }

        for (int i = 0; i < k; i++) {
            result[i] = points[result[i].x];
        }

        return result;
    }
}
